package com.example.leetcode.prcatice;

public class Test279 {
    // 12 = 4 + 4 + 4   13 = 4 + 9
    public int numSquares(int n) {
        int [] dp = new int[n+1]; // dp[i]代表平法和为n的最小个数
        for (int i = 1;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for (int j =1;j * j<=i;j++){
                min = Math.min(min,dp[i - j*j]);  // 枚举（1，根号i的值） 为j 故还需要若干数构成 i - j的平方
            }
            dp[i] = min+1;
        }
        return dp[n];
    }
}
